#include <unordered_map>
using namespace std;
// 思路:用哈希表做索引其他数据结构存数据来补充哈希表不具备的性质
// 本体:哈希加链表,通过"使用就头插(O(1))"来确定末尾节点为待删除节点
struct Node
{
    Node(int _key = 0, int _val = 0, Node *_next = nullptr, Node *_prev = nullptr)
        : val(_key, _val), next(_next), prev(_prev)
    {
        ;
    }
    pair<int, int> val;
    Node *next;
    Node *prev;
};
struct DList
{
    void remove(Node *node)
    {
        if (node == head)
            head = nullptr;
        node->prev->next = node->next;
        node->next->prev = node->prev;
        node = nullptr;
        // delete node;
    }
    void move_to_front(Node *node)
    {
        if (node == head)
            return;
        node->prev->next = node->next;
        node->next->prev = node->prev;

        head->prev->next = node;
        node->prev = head->prev;
        node->next = head;
        head->prev = node;
        head = node;
    }
    Node *push_front(int key, int val)
    {
        Node *node = new Node(key, val);
        if (head == nullptr)
        {
            head = node;
            node->next = node->prev = node;
            return node;
        }
        head->prev->next = node;
        node->prev = head->prev;
        node->next = head;
        head->prev = node;
        return head = node;
    }
    Node *head = nullptr;
};
class LRUCache
{
private:
    int cap;
    int use;
    DList list;
    unordered_map<int, Node *> u_map;

public:
    LRUCache(int capacity)
    {
        cap = capacity;
        use = 0;
    }

    int get(int key)
    {
        auto it = u_map.find(key);
        if (it == u_map.end())
            return -1;
        list.move_to_front(it->second);
        return it->second->val.second;
    }

    void put(int key, int value)
    {
        auto it = u_map.find(key);
        if (it != u_map.end())
        {
            it->second->val.second = value;
            list.move_to_front(it->second);
        }
        else
        {
            if (use == cap)
            {
                u_map.erase(list.head->prev->val.first);
                list.remove(list.head->prev);
                use--;
            }
            u_map[key] = list.push_front(key, value);
            use++;
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */